/*
 * @lc app=leetcode.cn id=34 lang=cpp
 *
 * [34] 在排序数组中查找元素的第一个和最后一个位置
 */
#include "include.h"
// @lc code=start
class Solution {
// public:
//     vector<int> searchRange(vector<int>& nums, int target) {
//         // int start = -1;
//         // int end = -1;
//         // int targetNum = 0;
//         // for (int i=0;i<nums.size();i++){
//         //     if (nums[i]==target){
//         //         if (start==-1){
//         //             start=i;
//         //             end = i;
//         //             targetNum--;
//         //             }
//         //         targetNum++;
//         //     }
//         // }
//         // end += targetNum;
//         // vector<int> result;
//         // result.push_back(start);
//         // result.push_back(end);
//         // return result;

//         vector<int> res;
//         if (nums.size()==0){
//             res.push_back(-1);
//             res.push_back(-1);
//             return res;
//         }
//         if (nums.size()==1){
//             if (nums[0]==target){
//                 res.push_back(0);
//                 res.push_back(0);
//             } else{
//                 res.push_back(-1);
//                 res.push_back(-1);
//             }
//             return res;
//         }

//         int l = binarySearch(nums, target);
//         int r = binarySearchRight(nums, target);
//         res.push_back(l);
//         res.push_back(r);
//         return res;
//     }
//     int binarySearch(vector<int>& nums, int target){
//         int n = nums.size();
        
//         int currentHalf = n/2;
//         int left = n-1;
//         while(!(nums[left-1]<target and nums[left]==target)){
//             if (nums[left-1]<target and nums[left]>target){
//                 return -1;
//             }
            
//             left = currentHalf;
//             if (nums[left] > target){
//                 currentHalf = (currentHalf+0)/2;
//             } else{
//                 currentHalf = (currentHalf+n)/2;
//             }
//         }
//         return left;
//     }
//     int binarySearchRight(vector<int>& nums, int target){
//         int n = nums.size();
        
//         int currentHalf = n/2;
//         int left = 0;
//         while(!(nums[left+1]>target and nums[left]==target)){
//             if (nums[left+1]>target and nums[left]<target){
//                 return -1;
//             }

//             left = currentHalf;
//             if (nums[left] > target){
//                 currentHalf = (currentHalf+0)/2;
//             } else{
//                 currentHalf = (currentHalf+n)/2;
//             }
//         }
//         return left;
//     }
public:
    int binarySearch(vector<int>& nums, int target, bool lower) {
        int left = 0, right = (int)nums.size() - 1, ans = (int)nums.size();
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] > target || (lower && nums[mid] >= target)) {
                right = mid - 1;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }

    vector<int> searchRange(vector<int>& nums, int target) {
        int leftIdx = binarySearch(nums, target, true);
        int rightIdx = binarySearch(nums, target, false) - 1;
        if (leftIdx <= rightIdx &&
            rightIdx < nums.size() && 
            nums[leftIdx] == target && 
            nums[rightIdx] == target) {
            return vector<int>{leftIdx, rightIdx};
        } 
        return vector<int>{-1, -1};
    }
};
// @lc code=end

